МІНІСТЕРСТВО ОСВІТИ УКРАЇНИ
ДЕРЖАВНИЙ УНІВЕРСИТЕТ "ЛЬВІВСЬКА ПОЛІТЕХНІКА"
ЧИСЕЛЬНІ МЕТОДИ РОЗВ'ЯЗУВАННЯ СИСТЕМ
ЛІНІЙНИХ АЛГЕБРАЇЧНИХ РІВНЯНЬ
І Н С Т Р У К Ц І Я
до лабораторної роботи N 4
з курсу " Чисельні методи в інформатиці "
для студентів базового напрямку 6.08.04
"Комп'ютерні науки"
Затверджено
на засіданні кафедри
"Системи автоматизованого
проектування"
Протокол N 14 від 03.04.1997 р.
Львів 1999
ЧИСЕЛЬНІ МЕТОДИ РОЗВ'ЯЗУВАННЯ СИСТЕМ ЛІНІЙНИХ АЛГЕБРАЇЧНИХ РІВНЯНЬ. Інструкція до лабораторної роботи N 4 з дисципліни "Теоретичні основи САПР" для студентів базового напрямку 6.08.04 "Комп'ютерні науки" / Укл. Мотика І.І., Каркульовський В.І., Чура І.І. – Львів: Видавництво ДУ "Львівська політехніка", 1999. – 10 с.
Укладачі Мотика І.І., канд. техн. наук, доц.
Каркульовський В.І., канд. техн. наук, доц.
Чура І.І., канд. техн. наук, доц.
Відповідальний за випуск С.П.Ткаченко, канд. техн. наук, доц.
Рецензенти Федасюк Д.В., канд. техн. наук, доц.
Близнюк М.Б., канд. техн. наук, доц.
1. МЕТА РОБОТИ
Мета роботи – ознайомитись із чисельними методами розв'язування систем лінійних алгебраїчних рівнянь та їх практичним застосуванням.
2. ТЕОРЕТИЧНА ЧАСТИНА
Методи розв'язування систем лінійних рівнянь можна поділити на два типи: прямі, або точні, та ітераційні. Прямі методи дають можливість дістати розв'язок, виконавши скінченну апріорі відому кількість операцій. Якщо всі проміжні обчислення виконувати точно (без заокруглень), то отримаємо точний розв'язок. Ітераційні методи дають нескінченну послідовність наближених розв'язків, границі яких є розв'язком системи.
2.1. Прямі методи розв'язування систем лінійних алгебраїчних рівнянь
Із точних методів розв'язування систем лінійних рівнянь відомий з курсу лінійної алгебри метод Гаусса, реалізація якого за схемою єдиного ділення вимагає виконання n(4n2-3n-4)/6 арифметичних операцій. Розглянемо розв'язування систем лінійних рівнянь методом Гаусса за схемою Халецького, для реалізації якої необхідно n(2n-1) арифметичних операцій.
Система лінійних алгебраїчних рівнянь в матричному представленні має вигляд:
(1)
Матрицю коефіцієнтів А подаємо у вигляді добутку двох трикутних матриць, тобто:
А=СВ. (2)
Матриця С – нижня трикутна, В – верхня трикутна, причому діагональні коефіцієнти матриці В дорівнюють одиниці.
Підставимо (2) в (1):
CBx=d. (3)
Позначимо Bx=y і перепишемо (3) у вигляді:
Cy=d (4)
Розв'язок (4) називається прямим ходом методу Гаусса, розв'язок (3) – зворотним ходом.
Отже, першим кроком при розв'язуванні сформульованої задачі є розбиття матриці А на дві трикутні матриці С і В.
Коефіцієнти матриць С і В обчислюються послідовно. Спочатку обчислюється перший стовпець матриці С:
,
тоді обчислюється перший рядок матриці В:
і елемент , після чого – елементи другого стовпця матриці С:
тоді обчислюються елементи другого рядка матриці В:
і елемент:
і т.д.
Після того, як будуть обчислені елементи матриць С і В, а також вектор y, знаходять невідомі :
.
Алгоритм методу Гаусса за схемою Халецького має такий компактний вигляд:
2.2. Ітераційні методи розв'язування систем лінійних алгебраїчних рівнянь
2.2.1. Метод простої ітерації
Найпростішим ітераційним методом розв'язування систем лінійних рівнянь
ах=d (5)
є метод простої ітерації. Система рівнянь (5) перетворюється до вигляду:
x=вx+e, (6)
де
,
. (7)
Ітераційний процес записується у вигляді:
. (8)
Для збіжності методу простих ітерацій при довільному початковому наближенні ітераційного процесу (8) необхідно і достатньо, щоб всі власні значення матриці B були за модулем менші ...